package lesson10;

import java.util.Arrays;

public class PartitionExample {

		public static void main(String[] args) {
			
			int[] array = {10,8,6,23,34,34,7,56,22,11};
			System.out.println(Arrays.toString(array));
			//partition(array, 0, array.length-1);
			//quickSort(array, 0, array.length-1);
			int k = 2;
			int kthElem = quickSearch(array, 0, array.length-1, k-1);
			System.out.println(kthElem);
			System.out.println(Arrays.toString(array));
		}
		
		//start is the index of the first element in subarray to be partitioned
		//end is the index of the last element in subarray to be partitioned
		//returns the index of the pivot in this subarray
		public static int partition(int[] array, int start, int end)
		{
			//median method
			int first = array[start];
			int last = array[end];
			int mid = array[end/2];
			
			int pivot = -1;
			int pivotIndex = -1;
			if(first < mid && mid < last)
			{
				pivot = mid; 
				pivotIndex = end/2;
			}
			else
			if(first > mid && first < last)
			{
				pivot = first; 
				pivotIndex = start;
			}
			else
			{
				pivot = last;
				pivotIndex = end;
			}
			
			swap(array, start, pivotIndex);
			int storeIndex = start+1;
			
			for(int i = start+1; i <= end; i++)//we check all elements in the given range of the array
			{
				if(array[i] < pivot)
				{
					swap(array, storeIndex, i);
					storeIndex++;
				}
			}
			swap(array, start, storeIndex-1);
			return storeIndex-1;
		}
		
		private static void swap(int[] a, int i, int j) 
		{
			int temp = a[i];
			a[i] = a[j];
			a[j] = temp;
		}

		//start is the index of the first element in subarray to be partitioned
		//end is the index of the last element in subarray to be partitioned
		public static void quickSort(int[] array, int start, int end)
		{
			if(start>=end)
				return;
			int pivotIndex = partition(array, start, end);
			
			quickSort(array, start, pivotIndex-1);//sort left side of the array
			quickSort(array, pivotIndex+1, end);//sort right side of the array
			
		}
		
		//start is the index of the first element in subarray to be partitioned
		//end is the index of the last element in subarray to be partitioned
		//k - he Kth smallest element in the array		
		public static int quickSearch(int[] array, int start, int end, int k)
		{
			//partition from start to end
			int pivotIndex = partition(array, start, end);
			//check if the partitionIndex is equal to K
			if(pivotIndex == k)
				//if yes, then we have found our Kth smallest element
				return array[pivotIndex];
			else
			//if no:
			{
				if(pivotIndex < k)
				{
					return quickSearch(array, pivotIndex+1, end, k);
				}
				else //(pivotIndex > k)
				{
					return quickSearch(array, start, pivotIndex-1, k);
				}
			}
			
		}
		
		
		
		
		
		
		
		
		
		
		
		
		
		

		
		public static int[] partitionByFirst(int[] array)
		{

			int[] array2 = new int[array.length];
			
			int targetValue = array[0];
			
			int firstCounter = 0;
			int lastCounter = array.length-1;
			for(int i= 1; i < array2.length; i++)
			{
				if(array[i] < targetValue)
				{
					array2[firstCounter++] = array[i];
				}
				else
				{
					array2[lastCounter--] = array[i];
				}
			}
			array2[firstCounter] = targetValue;
			return array2;
		}
		
		
		
}
